1. Field of the Invention
The present invention relates to a circuit using an adaptive filter to estimate an unknown system, and in particular to an adaptive filter suitable for an echo canceller that cancels an echo that may be a problem in the case of long-distance lines having relatively long transmission delay and including devices that couple local two-wire to long-distance four-wire lines.
2. Description of the Related Art
System identification using an adaptive filter is performed by updating the coefficients wi(t) of the adaptive filter to estimate an output signal y(t) corresponding to an input signal x(t) of the system by using a difference e(t)=ŷ(t)xe2x88x92y(t), where ŷ(t) is an output of the active filter.
Taking a learning identification method or normalized LMS (least-mean square) method as an example of system identification method, a conventional echo cancellation method will be described hereafter. Here, it is assumed that an unknown system is an unknown echo path in the case where an echo is created when four-wire lines are converted to two-wire lines. The learning identification method has been described in xe2x80x9cAdaptive Filter Theoryxe2x80x9d by Simon Haykin (Prentice-Hall Information and System Sciences series, 1996).
Consider an adaptive FIR (Finite Impulse Response) filter with N taps, a pseudo echo or echo replica ŷ(t) that is an output of the filter at time instant t is represented by                                                         y              ^                        ⁡                          (              t              )                                =                                    ∑                              i                =                1                            N                        ⁢                          (                                                wi                  ⁡                                      (                    t                    )                                                  *                                  x                  ⁡                                      (                                          t                      -                      i                                        )                                                              )                                      ,                            (        1        )            
where wi(t) is a i-th filter coefficient at time instant t and x(t) is a reference signal at time instant t.
Echo cancellation is achieved by subtracting the pseudo echo ŷ(t) from an echo signal y(t) as follows:
e(t)=y(t)xe2x88x92ŷ(t)xe2x80x83xe2x80x83(2),
where e(t) is a residual signal.
The filter coefficient wi(t) is updated so as to minimize the residual signal e(t) as follows:
wi(t+1)=wi(t)xe2x88x92xcexc(t)e(t)x(txe2x88x92i)xe2x80x83xe2x80x83(3) and
xcexc(t)=xcexc0/PX(t)xe2x80x83xe2x80x83(4),
where xcexc(t) is a step size and xcexc0 is a positive constant that has an effect on convergence rate and PX(t) is power of a reference signal x(t). The power PX(t) Is represented by                               PX          ⁡                      (            t            )                          =                              ∑                          i              =              1                        N                    ⁢                                                    x                ⁡                                  (                                      t                    -                    i                                    )                                            2                        .                                              (        5        )            
As is apparent from the above-described equations (1) through (5), generation of pseudo echo, power calculation of reference signal, and update of filter coefficient need the increasing amount of computation and memory in proportion to N. Further, It is known that the convergence rate of LMS-base algorithm such as the learning identification method is inversely proportional to N (see xe2x80x9cAdaptive Filter Theoryxe2x80x9d by Simon Haykin, pp365-444, Prentice-Hall Information and System Sciences series, 1996).
On the other hand, a dispersive region in impulse response of an echo path is only a part of the impulse response region (see FIG. 7). To eliminate an echo, it is necessary to estimate such a dispersive region by adjusting N tap filter coefficients of the adaptive filter. However, it is usually unknown when a dispersive region appears and therefore N is determined on the assumption of longest time interval. Since a dispersive region is only a part of the impulse response region, the filter coefficients provide a fixed delay section and a convergence section where coefficients after the dispersive region converge to zero. For the filter coefficients converging to zero, it is not necessary to calculate the equations (1) and (3). Therefore, these steps can be omitted. In other words, waste can be eliminated by dividing the N taps into valid taps to be subjected to the filter calculation and invalid taps not to be subjected to the filter calculation.
There has been disclosed a system estimator having a matrix switch connected between a series of delay elements and a series of coefficient circuits in Japanese Patent Application Unexamined Publication No. 4-245810. The matrix switch is controlled such that the respective positions of the taps are exchanged to intensively allocate valid taps to the dispersive region, resulting in increased convergence rate and reduced memory.
As an improved one, there has been disclosed a system estimator having a matrix switch connected between blocked delay elements and blocked filter circuits in Japanese Patent Application Unexamined Publication No. 10-229324. Hereafter, the blocked structure and operation of this conventional system estimator will be described with reference to FIGS. 1 and 2.
Referring to FIG. 1, echo cancellation is achieved by a subtracter 904 subtracting a pseudo echo ŷ(t) that is an output of an adaptive filter from an echo signal y(t), that is, e(t) =y(t)xe2x88x92ŷ(t), as described before. An adaptation controller 911 updates the filter coefficients of the adaptive filter so as to minimize the residual signal e(t).
The adaptive filter is provided with n input signal blocks 909.1 through 909.n, m filter circuits 910.1 through 910.m, a matrix switch 905 that connects the n input signal blocks 909.1 through 909.n to the n filter circuits 910.1-910.m under control of a controller 906. An input signal x(t) Is divided into the n input signal blocks 909.1 through 909.n, each block including k input signals. Each of the m filter circuits 910.1-910.m inputs k signals through the matrix switch 905 and generates k filter coefficients corresponding to respective ones of the k signals.
The controller 906 monitors m blocks of filter coefficients to control the matrix switch 905 so as to select m blocks from n blocks and connect the selected blocks to respective ones of the m filter circuits.
Hereinafter, an input signal block that is connected to an appropriate one of the filter circuits 910.1 through 910.m by the matrix switch 905 is called xe2x80x9cvalid blockxe2x80x9d. On the other hand, an input signal block that is not connected to any of the filter circuits by the matrix switch 905 is called xe2x80x9cinvalid blockxe2x80x9d. Such a switching operation of valid and invalid blocks, that is, selection operation of taps, is performed by the controller 906 as follows:
Selection 1: selecting one of the valid blocks that Is to switch from valid to invalid: and
Selection 2: selecting one of the invalid blocks that is to switch from invalid to valid.
FIG. 2 shows the functional configuration of the controller 906 for performing the above selection operation: Selection 1 and Selection 2.
In the processing of Selection 1, a minimum coefficient power block detector 813 detects the filter number BN and the position information POS of a block connected to the filter circuit providing the minimum coefficient power. The detected position information POS is stored in a shift register (or FIFO) 814 to append it to a queue stored in the shift register 814,
In the processing of Selection 2, a maximum coefficient power block detector 820 detects the filter number BN and the position information POS of a block connected to the filter circuit providing the maximum coefficient power. The decision section 817 inputs the position information of a candidate from the shift register 814 and the position information corresponding to the filter circuit providing the maximum coefficient power from the maximum coefficient power block detector 820 and determines whether the candidate should switch from invalid to valid. For example, the determination is made depending on whether a difference between the position of the candidate and the position of the filter circuit providing the maximum coefficient power is smaller than a predetermined value (L). When it is determined that the candidate should switch from invalid to valid, the decision section 817 outputs the block number BN and the position information POS to a controller 815 to control the matrix switch 905. Contrarily, when it is determined that the candidate should not switch from invalid to valid, the decision section 817 outputs the position information to the shift register 814 to append it to a queue stored therein. In this manner, it is possible to allocate valid taps intensively to around taps providing the maximum power, resulting in increased convergence rate and high-speed estimation.
However, as shown in FIG. 2, a closed loop is formed between the shift register 814 and the decision section 817 such that the decision section 817 determines whether the candidate should switch from invalid to valid and, if the candidate should not switch from invalid to valid, then the decision section 817 outputs the position information to the shift register 814 to append it to a queue stored therein. Such a closed loop including the decision step makes the adaptive filter difficult to follow an irregular or sudden change of the unknown system, resulting in unstable estimation. For example, in the case where a dispersive region is dramatically changed from a position 1 to a position 2 as shown in FIG. 7, which may be caused by replacing the to-be-estimated system with another system, the adaptive filter fails to adapt to such a change.
In addition, according to the prior art, estimation of dispersive region is independently performed at the initial stage (see xe2x80x9cA fast convergence algorithm for adaptive FIR filters with coarsely located tapsxe2x80x9d by Seiji Ikeda, pp. 1525-1529, Proc. ICASSP""91, 1991). In other words, the conventional adaptive filer is designed without taking a great system change during operation into consideration. In this case, the above-described decision step would adversely influence the system estimation. For example, the convergence rate is greatly decreased.
Further, since the processing of Selection 1 is performed by detecting a block of taps providing the minimum coefficient power, there are cases where a block of taps to be valid is selected as an invalid one when the power of the block is small. Concretely, in the case where a strongly correlative signal such as a voice signal is used to estimate, the filter coefficients are more unstable than in the case where the white noise having no correlation is used to estimate. Therefore, a block of taps to be valid may be erroneously determined to be invalid and is appended to the queue of the shift register 814. This results in reduced convergence rate.
Furthermore, according to the prior art, it is difficult to estimate a system exhibiting a plurality of dispersive regions because it is unknown when a plurality of dispersive regions occur. It is not possible for a single maximum coefficient power block detector 820 to cope with a plurality of dispersive regions. To estimate a plurality of dispersive regions, a plurality of maximum coefficient power block detectors 820 are needed.
An object of the present invention is to provide an adaptive filter allowing rapid adaptation to a sudden and great change in a system to be estimated.
Another object of the present invention is to provide an adaptive filter ensuring stable and rapid convergence even in the case of strongly correlative signal such as voice signal.
Still another object of the present invention is to provide an adaptive filter allowing rapid adaptation to a change in a system to be estimated without the need of specific processing at the initial stage of estimation.
According to the present invention, an adaptive filter includes: N signal blocks obtained by dividing a serial input signal by K, wherein N, K is an integer greater than 1; M (M  less than N) filter circuits, each of which generates K filter coefficients for one of the N signal blocks a switch for connecting M signal blocks selected from the N signal blocks to respective ones of the M filter circuits; and a controller controlling interconnection of the switch based on the K filter coefficients generated by each of the M filter circuits. The controller includes: a memory for storing position information indicative of a signal block connected to each of the M filter circuits, power information obtained from the K filter coefficients generated by each of the M filter circuits; a selector for selecting one as an invalid block from the M signal blocks connected to the M filter circuits to determine position information indicative of a selected signal block as an invalid block and a corresponding filter circuit that has been connected to the selected signal block; a shift register for storing a queue of position information, wherein the position information indicative of the selected signal block is appended to the queue and position information Is output from a head of the queue; and a switch controller controlling the switch using the corresponding filter circuit determined by the selector and the position information received from the shift register.
The selector may select one as an invalid block from the M signal blocks connected to the M filter circuits position by selecting a plurality of first signal blocks having relatively great power and a plurality of second signal blocks having relatively small power, wherein one of the second signal blocks, which is most distant from the first signal blocks, is selected as the invalid block.
The selector may include: a power sorter for sorting position information currently corresponding to respective ones of the M filter circuits in order of descending power information; a position comparator for comparing position information of the first signal blocks having higher-order power with that of each of the second signal blocks having lower-order power to produce minimum position differences for respective ones of the second signal blocks; and a maximum selector for selecting a maximum one of the minimum position differences to determine the position information indicative of a selected signal block as an invalid block and a corresponding filter circuit that has been connected to the selected signal block.
The position comparator may include: a position subtracter provided for position information of each of the first signal blocks, for calculating a position difference between a corresponding first signal block and a corresponding second signal block; and a minimum selector for selecting a minimum position difference from absolute values of position differences calculated for respective ones of the first signal blocks.
The position comparator may include: a position subtracter provided for position information of each of the first signal blocks, for calculating a position difference between a corresponding first signal block and a corresponding second signal block; and a positive minimum selector for selecting a minimum position difference from positive ones of position differences calculated for respective ones of the first signal blocks.